/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * 求集合的子集合
 * 输入： nums = [1,2,3] 
 * 输出:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
 * 要求：输入数组元素不重复
 * </p>
 * 
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月24日
 */
public class SubSet {
    // 输出需要排序吗？
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null) {
            return result;
        }
        // 对数列进行排序
        Arrays.sort(nums);
/*//         分期摊还法
//         加入空集
        result.add(new ArrayList<Integer>());
        result = amortized(nums, result);*/
        
        //递归方法
        List<Integer> path = new ArrayList<Integer>();
        findSub(nums,0,path,result);
        
        return result;
    }
    /**
     * 递归方法查找子集合
     * @param nums
     * @param start
     * @param path
     * @param result
     * @author towan
     * 2015年5月24日
     */
    private void findSub(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        if(start>nums.length){
            return ;
        }
        //保留中间结果，而不是遍历完成数列才保存结果
        List<Integer> clone = new ArrayList<>(path);
        result.add(clone);
        for(int i=start;i<nums.length;i++){
            path.add(nums[i]);
            
            findSub(nums, i+1, path, result);
            //回退
            path.remove(path.size()-1);
        }
    }
    //分期摊还法
    public List<List<Integer>> amortized(int[] nums, List<List<Integer>> result) {
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> tmp = new ArrayList<List<Integer>>();
            for (List<Integer> list : result) {
                tmp.add(list);// 保留原有结果集
                List<Integer> clone = new ArrayList<Integer>(list);
                clone.add(nums[i]);// 原有结果加入到新元素
                tmp.add(clone);
            }
            result = tmp;
        }
        return result;
    }
    
    public static void main(String[] args) {
        int nums [] = {3,1,2};
        SubSet subSet = new SubSet();
        System.out.println(subSet.subsets(nums));
    }
}
